1. Field of the Invention
The present invention relates to a method, system and program for fractionally shifting data subject to a previous transformation.
2. Description of the Related Art
Digital images may use one or more bits to describe the color intensity at each pixel. The term “pixel” or “pel” as used herein refers to one or more intensity (luminance) and color (chrominance) inputs or bit values at a data point that represents data to be rendered (i.e., printed, displayed, etc.), where the data to be rendered may include, but is not limited to, images, text, composite images, graphs, collages, scientific data, video, etc. The pixels that represent an image in uncompressed format are arranged in a bit map data structure.
To conserve storage space and improve transmission speed, the chrominance component of image data is often reduced in the image because the eye is not that sensitive to color changes. However, luminance information may not be removed at the same rate as chrominance data because the eye is more sensitive to changes in the luminance intensity than the chrominance intensity. For example, to eliminate chrominance data, the digital image processor algorithm may express the chrominance for a group of neighboring pixels as a single chrominance value, which may comprise the average chrominance of surrounding pixels. This process is referred to as down sampling the chrominance. FIG. 1a illustrates how each two-by-one block of chrominance samples, where each sample is represented by a block with a blackened circle (“•”), can be downsampled and represented with a single chrominance value, represented by the circled “S”. This down sampling technique reduces the chrominance portion of the image at a ratio of 2:1. FIG. 1b illustrates a further down sampling that reduces the chrominance by a ratio of 4:1.
In digital image processing, a shift operation is commonly used to shift a portion of the image by translating a group of pixels in one or more rows or columns by one or more whole pixels in the horizontal and/or vertical directions. With prior art chrominance downsampling methods, an image's chrominance data may be stored in an initial image file on a particular grid while a second image file representing the same image has the chrominance data stored on a different grid, which is not aligned with the initial grid but is rather a translation of the first grid by fractions of the original grid units. FIG. 1b shows a downsampling of chrominance values “S” from the chrominance values provided in FIG. 1a. FIG. 1c shows the same image as FIG. 1b with the chrominance shifted to the left a half a grid unit, which comprises a fractional shift of the downsampled data in FIG. 1b (i.e., a quarter of the distance between chrominance samples.).
The fractional shift operation is a technique used in digital image processing operations such as motion detection, arbitrary rotation, scaling and translation. Fractional shifting is used to convert between different image sampling formats and improve the appearance of color images that have experienced chrominance reduction as part of a reduction or downsampling operation. When reproducing an image that has experienced chrominance downsampling, the image processor must reconstruct the chrominance values for all the down sampled pixels, e.g., the black dots shown in FIGS. 1a, b, c. This process is otherwise referred to as upsampling the chrominance pels to a higher sampling frequency. One technique for upsampling is to replicate the chrominance downsamples “S” to all the neighboring pixels replaced by the downsample “S”, e.g., the four black dots are replaced by the downsampled “S” in FIG. 1b. 
One implementation of fractional pel shifting is conversion between MPEG-1 chrominance data sampled with a 4:2:0 scheme as shown in FIG. 1b (MPEG-1 in FIG. 9.1) and MPEG-2 chrominance data sampled with the same 4:2:0 scheme as shown in FIG. 1c (MPEG-2 in FIG. 9.1). The MPEG-2 chrominance samples are situated on a grid which is identical to the MPEG-1 chrominance sample grid with the exception that the grid is shifted ½ original units left. Thus, in order to convert an MPEG-1 image of this type to an MPEG-2 image of this type a fractional shift is needed. The original block or bitmap of the chrominance component of pixel data that will be fractionally shifted can be viewed as a matrix of the chrominance values. Further details of MPEG compression are described in the book “MPEG: Video Compression Standard”, by J. L. Mitchell, W. B. Pennebaker, C. E. Fogg, and D. J. LeGall (Copyright 1997, Chapman & Hall), which publication is incorporated herein by reference in its entirety.
Since a fractional shift on two axes can be achieved by two separate one-dimensional fractional shifts, each on one axis, we consider only one-dimensional fractional shifts. Furthermore, a one-dimensional fractional shift of an entire two-dimensional grid of data can be achieved by performing a one-dimensional fractional shift on each row or column of data in that grid. Thus, we consider only the case where a fractional shift is desired on a row (column) of data. For the purposes of exposition, we assume that this row (column) of data samples can be grouped into m blocks, each block consisting of eight data samples. That is, the row (column) is divided into m 1 by 8 (or 8 by 1) vectors with the ith vector being referred to as Gi. Thus, the vector Gi includes the following elements (Gi,1, Gi,2 . . . Gi,8).
The fractional shift matrix operation utilizes up to three matrices A, B, C, whose values are shown in FIG. 2. Matrices A, B, C are 8×8 matrices. The variable γ in the A, B, C matrices is the amount of the fractional pel shift, where γ is between 0 and 1. The shifted data is comprised of a matrix of row (column) vectors Hi, that can be determined by the following equations (1) and (2) below, that use the matrices A, B, C shown in FIG. 2 in a matrix multiplication operation (“·”):Hk=A·Gk+B·Gk+1 for k=1, 2, . . . , m−1  (1)Hm=C·Gm  (2)
Additional implementations of a fractional pel shift different than those described above may also be utilized. One benefit of the above prior art fractional shift transform process is that a color image which has chrominance samples on a grid different than a specific implementation in a decoding program can have the chrominance samples first shifted to the appropriate grid and correctly decoded so as to avoid visually obvious shifts in the chrominance data which would otherwise occur.
Notwithstanding, there is a need in the art to provide improved techniques for performing a fractional shift transform process.